package ReversalLink;

import java.util.Iterator;

public class Linked implements Iterable<Integer>{
    private Node hand;
    private int size;
   static class Node {
        public int value;
        public Node next;

       public Node(int value, Node next) {
           this.value = value;
           this.next = next;
       }
   }

    public Linked() {
       hand = new Node(0,null);
    }

    public void addLast (int value) {
        Node p = hand;
        while (p.next != null) {
            p = p.next;
        }
        p.next = new Node(value, null);
        size++;
    }
    public void addFirst(int value) {
       hand.next = new Node(value,hand.next);
       size++;
    }

    public Linked reverseMethod1 (Linked linked) {
       Linked linked1 = new Linked();
        for (Integer integer : linked) {
            linked1.addFirst(integer);
        }
        return linked1;
    }

    public Linked reverseMethod2(Linked linked) {

        Linked linkedNew = new Linked();
        Node handNew = linkedNew.hand;
        while (hand.next != null) {

            //先头删
            Node temp = hand.next;
            hand.next = temp.next;
            //再头插
            Node tp = handNew.next;
            handNew.next = temp;
            temp.next = tp;
        }
        return linkedNew;
    }

    public Linked reverseMethod3(Linked linked) {
       Linked linked1 = new Linked();
       linked1.hand.next = reversion(linked.hand.next);
       return linked1;
    }

    public Node reversion (Node node) {
       if (node == null || node.next == null) {
           return node;
       }
       Node last = reversion(node.next);
       node.next.next = node;
       node.next = null;
       return last;
    }


    public Linked reverseMethod4(Linked linked) {
       linked.hand.next = dualPointers(linked.hand.next);
       return linked;
    }

    public Node dualPointers(Node hand) {
       Node o1 = hand;
       Node n1 = hand;
       Node o2 = o1.next;
       while (o2 != null) {
           o1.next = o2.next;
           o2.next = n1;
           n1 = o2;
           o2 = o1.next;
       }
       return n1;
    }

    @Override
    public Iterator<Integer> iterator() {
        return new Iterator<Integer>() {
            Node p = hand.next;
            @Override
            public boolean hasNext() {

                return p != null;
            }

            @Override
            public Integer next() {
                int k = p.value;
                p = p.next;
                return k;
            }
        };
    }
}

